package main

import "fmt"

// 双向链表节点
type DoubleListNode struct {
	Val  int
	Next *DoubleListNode //链表的后向指针域
	Prev *DoubleListNode //链表的前向指针域
}

// 双向链表
type DoubleList struct {
	Head *DoubleListNode //头节点
	Tail *DoubleListNode //尾节点
}

func NewDoubleList() *DoubleList {
	return &DoubleList{}
}

// 链表节点添加（头部）
func (dl *DoubleList) InsertAtStart(val int) {
	newNode := &DoubleListNode{Val: val}
	if dl.Head == nil && dl.Tail == nil {
		dl.Head = newNode
		dl.Tail = newNode
		return
	}

	//新节点添加到头部
	newNode.Next = dl.Head
	dl.Head.Prev = newNode
	dl.Head = newNode //更改链表的head节点

}

// 链表节点添加（尾部）
func (dl *DoubleList) InsertAtEnd(val int) {
	newNode := &DoubleListNode{Val: val}
	if dl.Head == nil && dl.Tail == nil {
		dl.Head = newNode
		dl.Tail = newNode
		return
	}
	//新节点添加到尾部
	dl.Tail.Next = newNode
	newNode.Prev = dl.Tail
	dl.Tail = newNode //更改链表的tail节点
}

// 双向链表遍历（从前往后）
func (dl *DoubleList) PrintAtStart() {
	cur := dl.Head
	for cur != nil {
		fmt.Printf("%d\t", cur.Val)
		cur = cur.Next
	}
	fmt.Println()
}

// 双向链表遍历（从后往前）
func (dl *DoubleList) PrintAtEnd() {
	cur := dl.Tail
	for cur != nil {
		fmt.Printf("%d\t", cur.Val)
		cur = cur.Prev //指针向前移动
	}
	fmt.Println()
}

// 删除双向链表的节点
func (dl *DoubleList) Delete(val int) {
	cur := dl.Head
	for cur != nil {
		if cur.Val == val {
			//删除节点为：头节点
			if cur.Prev == nil {
				dl.Head = cur.Next
				cur.Next = nil
				dl.Head.Prev = nil
				return
			}
			//删除节点为：尾节点
			if cur.Next == nil {
				dl.Tail = cur.Prev
				cur.Prev = nil
				dl.Tail.Next = nil
				return
			}
			//普通节点删除（删除节点为cur指向的当前节点）
			cur.Prev.Next = cur.Next
			cur.Next.Prev = cur.Prev
			return
		}
		cur = cur.Next
	}
}
func main() {
	head := &DoubleListNode{Val: 1}
	//1. 添加节点
	newNode1 := &DoubleListNode{Val: 2}
	head.Next = newNode1 //链表指针衔接:后向
	newNode1.Prev = head //链表指针衔接:前向

	newNode2 := &DoubleListNode{Val: 3}
	head.Next.Next = newNode2 //链表指针衔接:后向
	newNode2.Prev = head.Next //链表指针衔接:前向

	//2.遍历链表节点
	//2.1 向后遍历
	fmt.Println("********************* 向后遍历 ************************")
	fmt.Println(head.Val)
	fmt.Println(head.Next.Val)
	fmt.Println(head.Next.Next.Val)
	//2.2 向前遍历
	fmt.Println("********************* 向前遍历 ************************")
	cur := head.Next.Next
	fmt.Println(cur.Val)
	fmt.Println(cur.Prev.Val)
	fmt.Println(cur.Prev.Prev.Val)

	//3. 删除节点（删除值为2的节点）
	head.Next = head.Next.Next
	head.Next.Prev = head

	fmt.Println("#################  方法封装  #####################")
	//4. 添加链表节点（头部）
	root := NewDoubleList()
	root.InsertAtStart(1)
	root.InsertAtStart(2)
	root.InsertAtStart(3)
	root.InsertAtStart(4)
	root.InsertAtStart(5)

	//5. 添加链表节点（尾部）
	root.InsertAtEnd(10)
	root.InsertAtEnd(20)
	root.InsertAtEnd(30)
	root.InsertAtEnd(40)
	root.InsertAtEnd(50)

	fmt.Println("********************* 打印链表节点的值（从前往后） ***************************")
	//6. 打印链表节点的值（从前往后）
	root.PrintAtStart()

	fmt.Println("********************* 打印链表节点的值（从后往前） **************************")
	//7. 打印链表节点的值（从后往前）
	root.PrintAtEnd()

	//8. 删除链表中的节点
	root.Delete(5)
	root.PrintAtStart()

	root.Delete(50)
	root.PrintAtStart()

	root.Delete(30)
	root.PrintAtStart()

	root.Delete(100)
	root.PrintAtStart()

}
